\documentclass{acmsiggraph}                     % final
%\documentclass[annualconference]{acmsiggraph}  % final (annual conference)
%\documentclass[review]{acmsiggraph}            % review
%\documentclass[widereview]{acmsiggraph}        % wide-spaced review
%\documentclass[preprint]{acmsiggraph}          % preprint

%% Uncomment one of the five lines above depending on where your paper is
%% in the conference process. ``review'' and ``widereview'' are for review
%% submission, ``preprint'' is for pre-publication, and ``final'' is for
%% the version to be printed. The ``final'' variant will accept the
%% ``annualconference'' parameter, which changes the height of the space
%% left clear for the ACM copyright information.

%% The 'helvet' and 'times' packages define the typefaces used for
%% serif and sans serif type in this document. Computer Modern Roman
%% is used for mathematics typesetting. The scale factor is set to .92
%% to bring the sans-serif type in line with the serif type.

\usepackage[scaled=.92]{helvet}
\usepackage{times}

%% The 'graphicx' package allows for the inclusion of EPS figures.

\usepackage{graphicx}

%% use this for zero \parindent and non-zero \parskip, intelligently.

\usepackage{parskip}

%% Optional: the 'caption' package provides a nicer-looking replacement
%% for the standard caption environment. With 'labelfont=bf,'textfont=it',
%% caption labels are bold and caption text is italic.

\usepackage[labelfont=bf,textfont=it]{caption}

%% If you are submitting a paper to the annual conference, please replace
%% the value ``0'' below with the numeric value of your OnlineID.
%% If you are not submitting this paper to the annual conference,
%% you may safely leave it at ``0'' -- it will not be included in the output.

\usepackage{subfigure}
\usepackage{tikz}
\usepackage{pgf}
\usepackage{xcolor}
\usetikzlibrary{fadings}
\usepackage{overpic}
\usepackage[ruled,vlined]{algorithm2e}
\usepackage{mathrsfs}
\usepackage{multirow}

\onlineid{0}

%% Paper title.

\title{Image-based Lightweight Tree Modeling}

%% Author and Affiliation (single author).

%%\author{Roy G. Biv\thanks{e-mail: roy.g.biv@aol.com}\\Allied Widgets Research}

%% Author and Affiliation (multiple authors).

\author{Ruoxi Sun\thanks{e-mail: 07zanmato@tongji.edu.cn}\\Jinyuan Jia\thanks{jyjia@tongji.edu.cn}\\Hongyu Li\thanks{hyli@tongji.edu.cn}\\ Tongji University%
\and Marc Jaeger\thanks{e-mail:ed.marcjaeg@gmail.com}\\ CIRAD%
}

%% Keywords that describe your work.

\keywords{radiosity, global illumination, constant time}

%%%%%% START OF THE PAPER %%%%%%

\begin{document}

\teaser{
\begin{center}
\begin{minipage}[c]{0.2\textwidth}
\centering
    \includegraphics[width=\textwidth]{Figure/Systemoverview(a).jpg}
\end{minipage}%
\begin{minipage}[c]{0.2\textwidth}
\centering
    \includegraphics[width=\textwidth]{Figure/Systemoverview(b).jpg}
\end{minipage}%
\begin{minipage}[c]{0.2\textwidth}
\centering
    \includegraphics[width=\textwidth]{Figure/Systemoverview(c).jpg}
\end{minipage}%
\begin{minipage}[c]{0.2\textwidth}
\centering
    \begin{tabular}{|l|}
\hline
\multicolumn{1}{|c|}{\textbf{L-system}}\\
\hline\hline
Axiom;\\
Productions;\\
Parameters;\\
\hline
\end{tabular}
\end{minipage}%
\begin{minipage}[c]{0.2\textwidth}
\centering
    \includegraphics[width=\textwidth]{Figure/Systemoverview(d).jpg}
\end{minipage}%
    \\

\begin{minipage}[r]{\textwidth}
\centering
    \fbox{\shortstack[c]{Source\\images}}
    \mbox{\vector(1, 0){40}}
    \fbox{\shortstack[c]{Branching\\structure\\recovery}}
    \mbox{\vector(1, 0){40}}
    \fbox{\shortstack[c]{3D skeleton\\reconstruction}}
    \mbox{\vector(1, 0){40}}
    \fbox{\shortstack[c]{L-system\\extraction}}
    \mbox{\vector(1, 0){40}}
    \fbox{\shortstack[c]{Model\\generation}}
\end{minipage}%


\end{center}
   \caption{Overview of the proposed method.}
\label{fig:overview}
}

%% The ``\maketitle'' command must be the first command after the
%% ``\begin{document}'' command. It prepares and prints the title block.

\maketitle

%% Abstract section.

\begin{abstract}

This paper proposes an approach to extract L-system
from two tree images inversely. This approach is different from the
traditional way of constructing L-systems that normally requires
expertise in botany and coding. In this approach, a 3D skeleton
of the visible trunk is first recovered from two images. The parametric L-system is then extracted from the recovered
3D skeleton. The extracted L-system can faithfully preserve the
overall shape of the trunk and be used to generate realistic 3D tree
models. The L-system is also flexible in changing the generated
3D tree model or simulating the tree growth. Experiments show that the
method for inversely extracting L-system is feasible and promising.

\end{abstract}

%% ACM Computing Review (CR) categories.
%% See <http://www.acm.org/class/1998/> for details.
%% The ``\CRcat'' command takes four arguments.

\begin{CRcatlist}
  \CRcat{I.3.7}{Computer Graphics}%
{Three-Dimensional Graphics and Realism}{Virtual reality};
\end{CRcatlist}

%% The ``\keywordlist'' command prints out the keywords.
\keywordlist

%-------------------------------------------------------------------------
\section{Introduction}

%L-system is conceived as a mathematical theory of plant development and widely used in tree modeling.

Nowadays virtual reality techniques are widely used in web
applications, esp. virtual tour, virtual natural landscape
and virtual agriculture. It is well known that tree is a key component in the natural environment, thus
modeling trees plays an important role in these fields. For now, more
light-weighted and intelligent tree modeling methods are demanded
urgently. In aims of light-weighted modeling, some details of trees,
such as tiny branches and leaves, can be elided since usually they are insignificant in virtual applications. On the other
hand, vision methods are employed to model trees from images for
more intelligence.

The techniques for modeling trees can be roughly classified as
rule-based and image-based. Rule-based techniques use a set of
generative rules or grammar to create branches and leaves
iteratively. The representative of this class is L-system introduced
in~\cite{Lindenmayer68} for describing fractal objects. Now L-system
has been carefully studied and extended to different versions, e.g. the
parametric L-system~\cite{Prusinkiewicz90} and the differential
L-system~\cite{Prusinkiewicz93}. Rule-based techniques supply strong
controls to the form of trees and are able to create light-weighted
tree models, but expertise in botany
is normally required to adjust the parameter values and the results
are often too mechanical to be close to natural trees.

%In~\cite{Mech96, Prusinkiewicz94} and~\cite{Prusinkiewicz01},
%L-system was improved with more ability of simulating the
%interaction between plants and environment and more intuitive
%modeling. There are still some other rule-based techniques. An
%approach was introduced in~\cite{Honda71} to describe branching
%structure only using branching angles and relative ratios of branch
%lengths. This method was improved in~\cite{Aono84}by introducing
%attractors, inhibitors and variation of branching angles. The
%definition of tree skeleton, generation of the mesh, and recovery of
%limb barks are introduced in~\cite{Bloomenthal85}.
%In~\cite{Oppenheimer86}, several parameters such as stem taper rates
%and helical twist are later added to control stem shape.
%In~\cite{de95} an approach using parameters and rules faithful to
%botanical structure and development was introduced. Another system
%with dozens of parameters which are un-strict obeying botanical
%principles but easy to use by the users was proposed
%in~\cite{Weber95}.

Image-based techniques try to recover the tree geometries directly
using single or multiple photographs. Visual hull was reconstructed
from several images to aid the tree modeling in \cite{Reche04} and~\cite{Shlyakhter01}. In addition, Quan et al. proposed an
approach in \cite{Quan06} to recover plant geometry from
reconstructed point clouds. Image-based techniques are highly
intelligent and able to assure reality of the models because the
models are reconstructed from real images. Nevertheless, it is
inconvenient for users to change the tree models, and the result can
severely impede the transmission in the network due to the huge
amount of data.

To avoid the drawbacks of current techniques, a new approach is proposed
in this paper. This method combines rule-based and image-based
techniques and is able to intelligently model light-weighted trees. In this
approach, 3D skeleton of a tree trunk and the branching structure
are reconstructed from images using binocular vision methods, and the parametric
L-system is extracted from the reconstructed 3D skeleton and
branching structure. The extracted L-system could be
used to model vivid trees and simulate the tree growth.

In sum, the proposed approach can be divided into four steps, as illustrated in
Figure~\ref{fig:overview}. Each step is outlined as follows:

\begin{itemize}
\item \textbf{Branching structure recovery:}
Branching structure describes the logical structure of the tree,
i.e. the parent-child relationship between the branches. The tree
trunk and its 2D skeleton are first extracted from a source image. The
branching structure is then recovered from the 2D skeleton.
\item \textbf{3D skeleton reconstruction:} Using binocular vision methods,
the 3D skeleton of the tree trunk is reconstructed.
\item \textbf{L-system extraction:} The axiom and production set of the
L-system are extracted from the 3D skeleton. The parameters of the L-system are computed as well.
\item \textbf{Model generation:} The tree model is built by the extracted L-system. The L-system is adjustable
for other usages (e.g. tree growth simulation).
\end{itemize}

\begin{figure}
  \centering
  \subfigure[]{
    \label{fig:preprocessing:a} %% label for first subfigure
    \includegraphics[scale=0.5]{Figure/Preprocessing(a).jpg}}
  \hfill
  \subfigure[]{
    \label{fig:preprocessing:b} %% label for second subfigure
    \includegraphics[scale=0.5]{Figure/Preprocessing(b).jpg}}
  \hfill
  \subfigure[]{
    \label{fig:preprocessing:c} %% label for first subfigure
    \includegraphics[scale=0.5]{Figure/Preprocessing(c).jpg}}
  \hfill
  \subfigure[]{
    \label{fig:preprocessing:d} %% label for second subfigure
    \includegraphics[scale=0.5]{Figure/Preprocessing(d).jpg}}
  \caption{(a) Original image; (b) Segmentation; (c) Distance transform; (d) Non-maximum suppression.}
  \label{fig:preprocessing} %% label for entire figure
\end{figure}

%-------------------------------------------------------------------------
\section{Branching structure recovery}
\label{sec:Pre-processing}

To recover the branching structure, a tree
trunk must be first extracted from a source image. That is actually a bipartition
process. There exist a number of methods to complete this task, such
as $SWA$~\cite{nature/Sharon06}, and
Ncut~\cite{DBLP:journals/pami/ShiM00}. This study borrows the idea
of $SWA$ to segment the tree trunk. An example is shown in
Figure~\ref{fig:preprocessing}. Panels (a) and (b) are respectively
the source image and the corresponding tree trunk. For details of
the $SWA$ algorithm, please refer to~\cite{nature/Sharon06}.

After bipartition, a thinning algorithm is needed to obtain the
2D skeleton of the tree trunk. Skeleton is the best way to describe
the main character of a tree. It preserves the morphological
feature of a tree and is easy for processing. Our thinning approach is
based on the distance transform~\cite{Borgefors86}. The distance
transform of an image is defined as a new image in which every
output pixel is set to a value equal to the distance to the nearest
zero pixel in the input image. All points that have the maximum
distance in the gradient direction compose the skeleton of the
image, as shown in Figure~\ref{fig:preprocessing:c}. The
``Non-maximum suppression'' method \cite{Canny86} is applied on the
distance to filtering the non-skeleton points. The gradient
directions at crossing points are ambiguous so the skeleton
would break at crossing points, as shown in
Figure~\ref{fig:preprocessing:d}. As a result, the skeleton is
divided into several continuous areas, each of which corresponds to
a branch segment.

Once all branches are obtained, the remaining work is to find the
parent for each branch. To do this, two kinds of crossing points
have to be considered. One is the real branching point of
the tree and the other is the overlapping point of two
individual branches. The latter essentially contains the fake
branching relationship caused by visual errors.
Our strategy of finding the parent for a branch is realized through analyzing both the distance and angle between them.

A branch can be represented by a starting point $S$ and a
terminal point $T$. In a continuous skeleton, the way of
determining the starting point $S$ is to compute the spatial
distance from the current point to the tree root. The point with the
smaller distance is considered as $S$, the other is $T$. Now we use
an example to explain our strategy of handling overlapping points,
as shown in Figure~\ref{fig:branchingstructure}. For branch $b$
with the starting point $S_b$, a circle with radius $d$ is first
drawn at $S_b$. Branches with an end point falling in this
circle are considered as candidate parents of $b$. Therefore, $c_1$ and $c_2$ are candidate parents of $b$, however,
$b'$ is not. $b''$ cannot be selected as a candidate parent of $b$
because it is not connected to $b$ in the segmented image.

The angle difference is the other significant factor considered in our strategy.
Assuming that the angle from a branch to its parent is the least, the process of searching the parent begins
from the inverse direction of the branch, proceeds on both sides of this direction, and stops until the first candidate appears.
This candidate parent will be considered as the final parent.
For instance, in
Figure~\ref{fig:branchingstructure}, $c_1$ is the first candidate parent appearing on both sides of the inverse direction of $S_bT_b$, so the
parent of $b$ is $c_1$. As such, $c_2$ is identified as the parent of branch $b'$.

\begin{figure}
  \centering
  \begin{overpic}{Figure/binary.jpg}

\begin{tikzpicture}[path fading=south]

%help line
%\draw[help lines, gray] (-3,-3) grid (5,5);

%circle bkg
\fill[blue, very nearly transparent] (2,2) circle(2);

%angel bkg
\fill[rotate around={30 - 45:(2,2)}, gray, semitransparent, path fading, fading transform={rotate=-45}] (2,2) -- (2,-3) arc (-90:-150:5);

%circle
\draw[blue, dashed] (2,2) circle(2);

%radius
\draw[rotate around={90:(2,2)}, blue, dashed, ->] (2,2) -- node[above] {$d$} (2,0);

%rays
\draw[rotate around={-75:(2,2)}, black!80, dashed, ->] (2,2) to node[above] {$r_1$} (2,-3);
\draw[rotate around={-15:(2,2)}, black!80, dashed, ->] (2,2) to node[right] {$r_2$} (2,-3);
\draw[rotate around={-45:(2,2)}, black!80, dashed, ->] (2,2) to (2,-3);

%arcs
\draw[rotate around={-45:(2,2)}, black!80, dashed] (2,-0.5) arc (-90:-120:2.5);
\draw[rotate around={-45:(2,2)}, black!80, dashed] (2,-0.7) arc (-90:-60:2.7);
\node[black!80] (alpha1) at (0.1,0.8) {$\alpha$};
\node[black!80] (alpha2) at (0.8,-0.1) {$\alpha$};

%branch
\draw[line width=1] (2,2) to node[anchor=south east] {$b$} (4,4);
\node[anchor=south east] (sb) at (2,2) {$S_b$};
\node[anchor=south east] (tb) at (4,4) {$T_b$};
\fill (2,2) circle (2pt);
\fill (4,4) circle (2pt);

%branch'
\draw[black!80, line width=1] (1,2) to node[above] {$b'$} (-2,3);
\node[black!80, above] (sb') at (1,2) {$S'_{b}$};
\node[black!80, above] (tb') at (-2,3) {$T'_{b}$};
\fill[black!80] (1,2) circle (2pt);
\fill[black!80] (-2,3) circle (2pt);

%branch''
\draw[black!80, line width=1] (-2,0) to node[above] {$b''$} (0.5,1.25);
\node[black!80, above] (sb') at (-2,0) {$S''_{b}$};
\node[black!80, right] (tb') at (0.5,1.25) {$T''_{b}$};
\fill[black!80] (-2,0) circle (2pt);
\fill[black!80] (0.5,1.25) circle (2pt);

%c1
\draw[red, line width=1] (0,-2) to node[left] {$c_1$} (1.5,1);
\node[red, left] at (0,-2) {$S_1$};
\node[red, above] at (1.5,1) {$T_1$};
\fill[red] (0,-2) circle (2pt);
\fill[red] (1.5,1) circle (2pt);

%c2
\draw[green, line width=1] (4.5,-0.5) to node[above] {$c_2$} (2.5,1);
\node[green, above] at (4.5,-0.5) {$S_2$};
\node[green, above] at (2.5,1) {$T_2$};
\fill[green] (4.5,-0.5) circle (2pt);
\fill[green] (2.5,1) circle (2pt);

\end{tikzpicture}
\end{overpic}
\caption{Finding the parent for branch $b$. Gray thick lines are
branches in the segmented image. $b$, $b'$, $b''$, $c_1$ and $c_2$
are extracted skeletons. Finally $c_1$ is chosen as the
parent of $b$ due to the smaller distance and angle difference.}
  \label{fig:branchingstructure} %% label for entire figure
\end{figure}

%-------------------------------------------------------------------------
\section{3D skeleton reconstruction}

Since a branch is represented by a starting point and a terminal
point, 3D skeleton reconstruction is equivalent to estimating the 3D
positions of both points. Two-view geometry~\cite{Hartley00} gives a
theory to do this work.

\subsection{Reconstruction}
\label{sec:Mathematics}

The 3D coordinates $M$ of a point can be calculated through its 2D
coordinates in two images, $m_1$ and $m_2$, and the projection
matrices, $P_1$ and $P_2$.
\begin{eqnarray}
\label{eqn:mPM}
m_1 = P_1 M \nonumber\\
m_2 = P_2 M
\end{eqnarray}

Matrices $P_1$ and $P_2$ are the key of the 3D reconstruction of a
point. They are related to the intrinsic and extrinsic parameters of
cameras~\cite{Hartley00},
\begin{eqnarray}
\label{eqn:PKRt}
P_1 = K [I, \vec{0}] \nonumber\\
P_2 = K [R, \vec{t}]
\end{eqnarray}
where $K$ is the internal parameter, $I$ an identity matrix,
$\vec{0}$ a zero vector, $R$ the rotation matrix, and $\vec{t}$ the
translation vector between two cameras.

In our experiments, cameras have been fully calibrated so $K$ is
known. $R$ and $\vec{t}$ can be calculated through $K$ and the
correspondence between two images. The correspondence essentially
describes the match of feature points (e.g. SIFT
features~\cite{Lowe04}) and is used to estimate the fundamental
matrix $F$ using the RANSAC method~\cite{Fischler81}. In addition,
the essential matrix $E$ is also needed to solve for $R$ and
$\vec{t}$. $E$ is computed as follows,
\begin{equation}
\label{eqn:EKF}
E = K^T F K
\end{equation}
where $K^T$ is the transpose of $K$. Then $\vec{t}$ and $R$ are
respectively computed through the following equations,
\begin{equation}
\label{eqn:Et}
E E^T = [\vec{t}]_\times [\vec{t}]^T_\times
\end{equation}
\begin{equation}
\label{eqn:EtR}
E = [\vec{t}]_\times R
\end{equation}
where $[\vec{t}]_\times$ is the skew-symmetric matrix of $\vec{t}$.

\subsection{Branch correspondence}

%A branch can be reconstructed by recovering the 3D position of its
%starting terminal point. As mentioned in
%Section~\ref{sec:Mathematics}, reconstructing a 3D point requires a
%pair of matching 2D points in two images.
Our approach recovers the branching structure only from one source
image, the branching structure in the other image is obtained
through branch correspondence. The correspondence is actually to find starting and terminal
points of branches in the second image matching corresponding to
ones in the first image.

During branch correspondence, a point-to-line mapping is used to
shrink the searching area of matching points. This mapping is
embedded in the fundamental matrix $F$. A point $m_1$ in one image
is mapped to a line $l_2$ in the other through the transformation
matrix $F$,
\begin{equation}
\label{eqn:lFm} l_2 = F m_1.
\end{equation}
It means that the matching point $m_2$ of $m_1$ is supposed to lie
on $l_2$. This constraint condition is quite strong and helps reduce
the searching scope from the whole image to a line. Specifically,
the ``sum of absolute difference'' method (SAD)~\cite{Bradski08} is
used to search for $m_2$ along $l_2$. Once $m_1$ and $m_2$ are
matched, they can be substituted into Equation \ref{eqn:mPM} to
compute the 3D coordinates. When all branches are matched,
3D skeletons of a tree are with ease reconstructed.

%-------------------------------------------------------------------------
\section{L-system extraction}
\label{sec:lsystemextraction}

Three elements of parametric L-system is \textbf{axiom}, \textbf{productions} and \textbf{parameters}.
%In this section a extraction method is proposed to extract all the three elements from the reconstructed tree skeleton.
The logical structure of tree branches is decided by axiom and productions.
The branching context is represented by the rewriting mechanism of the productions applied on the axiom.
On the other hand, the details of the tree shape are decided by parameters.
Parameters record branch lengths, widths and angles at every position.
In this section a extraction method is proposed to extract all the three elements from the reconstructed tree skeleton.

\begin{figure}
  \centering
\begin{tikzpicture}
[grow'=up,
level 1/.style={level distance=48},
level 2/.style={level distance=32},
level 3/.style={level distance=32},
level 4/.style={level distance=32},
level 5/.style={sibling distance=10, level distance=32}]
\coordinate
child[red]{
    child[orange, sibling distance=10 * 7]{
        child[green, sibling distance=10 * 2]{
            child[blue, sibling distance=10 * 3]{
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                edge from parent
                node[left]{$8$}
            }
            child[blue, sibling distance=10 * 2]{
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                edge from parent
                node[right]{$9$}
            }
            edge from parent
            node[left]{$3$}
        }
        child[green, sibling distance=10 * 2.5]{
            child[blue, sibling distance=10 * 1]{
                %node{$t$}
                edge from parent[dashed]
            }
            child[blue, sibling distance=10 * 1]{
                %node{$t$}
                edge from parent[dashed]
            }
            edge from parent
            node[right]{$4$}
        }
        edge from parent
        node[left]{$1$}
    }
    child[orange, sibling distance=10 * 11]{
        child[green, sibling distance=10 * 5.5]{
            child[blue, sibling distance=10 * 2]{
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                edge from parent
                node[left]{$10$}
            }
            child[blue, sibling distance=10 * 2]{
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                edge from parent
                node[right]{$11$}
            }
            edge from parent
            node[below]{$5$}
        }
        child[green, sibling distance=10 * 0]{
            child[blue, sibling distance=10 * 2.5]{
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                edge from parent
                node[left]{$12$}
            }
            child[blue, sibling distance=10 * 0]{
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                edge from parent
                node[anchor=south east]{$13$}
            }
            child[blue, sibling distance=10 * 2.5]{
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                child[purple]{
                    %node{$t$}
                    edge from parent[dashed]
                }
                edge from parent
                node[right]{$14$}
            }
            edge from parent
            node[left]{$6$}
        }
        child[green, sibling distance=10 * 4]{
            child[blue, sibling distance=15 * 1]{
                %node{$t$}
                edge from parent[dashed]
            }
            child[blue, sibling distance=10 * 1]{
                %node{$t$}
                edge from parent[dashed]
            }
            edge from parent
            node[below]{$7$}
        }
        edge from parent
        node[above]{$2$}
    }
    edge from parent
    node[left]{$r$}
};
\end{tikzpicture}
\caption{The illustration of a branching structure. Dashed lines represent terminal branches,
others are internal branches. IDs of internal branches are marked
out and the ID $t$ of terminal branches is omitted here.}
\label{fig:skeleton} %% label for entire figure
\end{figure}

The extraction of axiom and production follows the next two steps:
\begin{itemize}
\item Scan the branching structure of the reconstructed 3D skeleton first bottom-up then left-right
to build a initial production set $\mathscr{P}$. Let the root branch $r$ to be the axiom.
\item Find the similar substructures in the branching structure of the reconstructed 3D skeleton,
record them in a table $\mathscr{R}$. Reduce $\mathscr{P}$ according to $\mathscr{R}$.
\end{itemize}
Reducing $\mathscr{P}$ makes two points of significance:
\begin{itemize}
\item Each production in $\mathscr{P}$ represents a unique substructure,
which makes $\mathscr{P}$ simplest but enough to represents the whole branching structure.
\item Productions in $\mathscr{P}$ is completely recursive,
which results in the capability of infinite rewriting process.
\end{itemize}
The extraction algorithm will be illustrated by the sample skeleton
in Figure~\ref{fig:skeleton}.

Before extracting productions, we need to define two categories of
branches first: the branches with no children are \textbf{terminal},
the others are \textbf{internal}.
As shown in Figure~\ref{fig:skeleton}, branches with dashed lines
are terminal, the others are internal.
Each internal branch is associated
with a unique ID. Terminal branches have a common ID $t$ because
they have the same structure.
Numbers (or letter) beside the branches in Figure~\ref{fig:skeleton} are their IDs.
A production has the form of
``$predecessor \rightarrow successor$'', where predecessor
represents the ID of a parent branch and successor is a string
composed of IDs of children branches belonging to predecessor.
The branching structure of
the tree trunk can be fully translated into a set of productions
$\mathscr{P}$. All productions in $\mathscr{P}$ are sorted in the
specified order, first bottom-up, then left-right.
For the
convenience of expression, the production in $\mathscr{P}$ whose
predecessor equals to $p$ is denoted as $\mathscr{P}(p)$, the $i$th
production in $\mathscr{P}$ as $\mathscr{P}[i]$, the predecessor and successor of
a production $\mathscr{P}[i]$ as $\mathscr{P}[i].p$ and $\mathscr{P}[i].s$, and the $i$th ID in a successor $s$ as
$s[i]$.
The result of initial $\mathscr{P}$ is listed in Table~\ref{tbl:prereduction}.
In addition, we define \textbf{equivalent} productions as ones with
the same successors. Equivalent productions follow a property: if two productions $\mathscr{P}[i]$ and $\mathscr{P}[j]$
are equivalent, $\mathscr{P}[j].p$ appearing in the successor of a
production can be replaced by $\mathscr{P}[i].p$. In this case,
$\mathscr{P}[j]$ can be deleted from $\mathscr{P}$ for
simplification. This deletion can be repeated until there are no
equivalent productions in $\mathscr{P}$. The process of deletion is
called pre-reduction. Table~\ref{tbl:reduction} also lists the result after pre-reduction.

\begin{table}
\begin{center}
\subtable{
\centering
\begin{tabular}{|c|l|}
\hline
\multicolumn{1}{|c|}{$\textbf{ID}$} & \multicolumn{1}{|c|}{$\mathscr{P}(\textbf{ID}).s$}\\
\hline\hline
$r$ & $\{1, 2\}$\\
$1$ & $\{3, 4\}$\\
$2$ & $\{5, 6, 7\}$\\
$3$ & $\{8, 9\}$\\
$4$ & $\{t, t\}$\\
$5$ & $\{10, 11\}$\\
$6$ & $\{12, 13, 14\}$\\
$7$ & $\{t, t\}$\\
$8$ & $\{t, t\}$\\
$9$ & $\{t, t, t\}$\\
$10$ & $\{t, t\}$\\
$11$ & $\{t, t\}$\\
$12$ & $\{t, t\}$\\
$13$ & $\{t, t, t\}$\\
$14$ & $\{t, t\}$\\
\hline
\end{tabular}
}
\subtable{
\centering
\begin{tabular}{|c|l|}
\hline
\multicolumn{1}{|c|}{$\textbf{ID}$} & \multicolumn{1}{|c|}{$\mathscr{P}(\textbf{ID}).s$}\\
\hline\hline
$r$ & $\{1, 2\}$\\
$1$ & $\{3, 14\}$\\
$2$ & $\{5, 6, 14\}$\\
$3$ & $\{14, 13\}$\\
$5$ & $\{14, 14\}$\\
$6$ & $\{14, 13, 14\}$\\
$13$ & $\{t, t, t\}$\\
$14$ & $\{t, t\}$\\
\hline
\end{tabular}
}
\end{center}
\caption{Left: initial $\mathscr{P}$; Right: after pre-reduction.}
\label{tbl:prereduction}
\end{table}

Next work is to analyze the rest productions to find those productions
who have \textbf{similar} structures.
Similar structures mean those branches who have the same sequel-context
in the tree skeleton unless one of the branch reached to a terminal branch.
For instance, 


However, the production set $\mathscr{P}$ after pre-reduction is
still unable to forecast the future structure of the tree trunk
because the process of rewriting new structures always stops at terminal branches.
To produce new branches, terminal branches have to be replaced with
internal branches. Besides, the set $\mathscr{P}$ includes many redundant
productions. To simplify productions, internal branches having the
similar successor need to be induced. This paper
proposes a \textbf{reduction} method to complete both tasks
mentioned above. Reduction is actually an iterative process of
reducing productions, and complies with the below statements:
\newtheorem{dfn}{Statement}
\begin{dfn}
\label{dfn:terminalreduction}
If $b_1$ is a terminal branch, $b_1$ can be \textbf{reduced} by any branch.
\end{dfn}
\begin{dfn}
\label{dfn:nonterminalreduction} For internal branches $b_1$ and
$b_2$, if $\mathscr{P}(b_1).s$ has the same length as
$\mathscr{P}(b_2).s$, and $\mathscr{P}(b_1).s[i]$ can be
\textbf{reduced} by $\mathscr{P}(b_2).s[i]$ where $i = 0, 1 \cdots$,
$b_1$ can be \textbf{reduced} by $b_2$.
\end{dfn}

A reduction table $\mathscr{R}$ is needed during reduction. It lists
branches that are capable to replace others. Moreover, branches in a row of the
reduction table cannot replace each other.
Algorithm~\ref{alg:addtoreductiontable} $ART$ (abbr. for
``Add to Reduction Table'') in detail states the process of finding the
reduction relation and adding branches to $\mathscr{R}$.

%$\mathscr{R}(b)$ means the list in the second column of the table
%where the value of first column is $b$ and $\mathscr{R}(b)[i]$ means
%the $i$th branch in $\mathscr{R}(b)$.

\begin{algorithm}
\caption{ART} \label{alg:addtoreductiontable}

\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}

\Input{$b_1$ and $b_2$ (two internal branches), $\mathscr{R}$ (a reduction table)}

\BlankLine
\If{$b_1$ equals to $b_2$}{
    \Return;
}
\If{$b_2$ can be reduced by $b_1$}{
    exchange the values of $b_1$ and $b_2$;
}
\If{$b_1$ can be reduced by $b_2$}{
    $list \leftarrow \mathscr{R}(b_1)$;\\
    $reduced \leftarrow false$;\\
    \ForEach{$list[i]$}{
        \If{$list[i]$ can be reduced by $b_2$}{
            \textbf{ART}($list[i]$, $b_2$, $\mathscr{R}$);
            \Return;
        }
        \ElseIf{$b_2$ can be reduced by $list[i]$}{
            \textbf{ART}($b_2$, $list[i]$, $\mathscr{R}$);\\
            $list[i] \leftarrow b_2$;\\
            $reduced \leftarrow true$;
        }
    }
    \If{$reduced$ equals to $false$}{
        add $b_2$ to $list$;
    }
    $\mathscr{R}(b_1) \leftarrow list$;
}
\end{algorithm}

\newtheorem{crl}{Corollary}
\begin{crl}
\label{crl:reductionrelationship} If $b_1$ and $b_2$ \textbf{cannot} be
reduced by each other, and $b_1$ \textbf{can} be reduced by $b_3$, $b_2$ \textbf{cannot} be
reduced by $b_3$.
\end{crl}

The validity of the first $if$ in the $foreach$ block in
Algorithm~\ref{alg:addtoreductiontable} is ensured by
Corollary~\ref{crl:reductionrelationship}. There will not be any
other branch in $list$ that can be reduced by $b_2$ if $list[i]$
can be reduced by $b_2$. So there is a $return$ after the recursive
calling of $ART(list[i], b_2, \mathscr{R})$.
For a structure in the lower level of a tree, this algorithm can
find its similar structure in the higher level. For instance, branch $6$ in Figure~\ref{fig:skeleton} is considered by this algorithm as being similar to branch $13$.

A terminal branch can be reduced by a similar internal branch in our
algorithm. However, if a terminal branch does not have the similar
structure in the lower level, it can be reduced by the root
branch $r$.
\begin{table}[h]
\begin{center}
\begin{tabular}{|c|l|l|}
\hline
\multicolumn{1}{|c|}{$\textbf{ID}$} & \multicolumn{1}{|c|}{$\mathscr{P}(\textbf{ID}).s$} & \multicolumn{1}{|c|}{$\mathscr{R}(\textbf{ID})$}\\
\hline\hline
$r$ & $\{1, 2\}$ & $\{\}$\\
$1$ & $\{3, 14\}$ & $\{\}$\\
$2$ & $\{5, 6, 14\}$ & $\{\}$\\
$3$ & $\{14, 13\}$ & $\{r\}$\\
$5$ & $\{14, 14\}$ & $\{1\}$\\
$6$ & $\{14, 13, 14\}$ & $\{2\}$\\
$13$ & $\{t, t, t\}$ & $\{6\}$\\
$14$ & $\{t, t\}$ & $\{3, 5\}$\\
\hline
\end{tabular}
\end{center}
\caption{$\mathscr{P}$ and $\mathscr{R}$ after pre-reduction.}
\label{tbl:reduction}
\end{table}

The final reduction table $\mathscr{R}$ will be used to reduce
$\mathscr{P}$. The reduction process is presented in
Algorithm~\ref{alg:reduce}.
\begin{algorithm}
\caption{Reduction} \label{alg:reduce} \SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\Input{$\mathscr{P}$ (production set), $\mathscr{R}$ (reduction table), $r$ (the ID of the root branch)}
\BlankLine
$n \leftarrow$ size of $\mathscr{P}$;\\
\For{$i = n - 1$ \emph{\KwTo} $0$}{
    $list \leftarrow \mathscr{R}(\mathscr{P}[i].p)$;\\
    find the branch $b$ in $list$ who has the lowest level in the tree;\\
    replace all $\mathscr{P}[i].p$ in the successor of any production with branch $b$;
}
replace the rest terminal branches with $r$;
\end{algorithm}
A result of Algorithm~\ref{alg:reduce} is that no terminal
branches appear in the successor of any production in $\mathscr{P}$.
In addition, since some productions lose the connectivity to the root branch, they are deleted from $\mathscr{P}$.
The final axiom $r$ and
the production set $\mathscr{P}$ can be extracted after running
Algorithm~\ref{alg:reduce}. Table~\ref{tbl:lsystem} shows the
extracted axiom and productions of the branching structure in
Figure~\ref{fig:skeleton}.
\begin{table}[h]
\begin{center}
\begin{tabular}{|c|l|}
\hline
$\textbf{Axiom}$ & \multicolumn{1}{|c|}{$\mathscr{P}$}\\
\hline\hline
& $r \rightarrow \{1, 2\}$;\\
{$r$} & $1 \rightarrow \{r, r\}$;\\
& $2 \rightarrow \{1, 2, r\};$\\
\hline
\end{tabular}
\end{center}
\caption{The extracted axiom and productions of Figure~\ref{fig:skeleton}.}
\label{tbl:lsystem}
\end{table}

\subsection{Parameter extraction}

To better control the shape of the tree trunk, a set of parameters should be introduced to extend the original L-system to a parametric version. These parameters are:

\begin{enumerate}
\item \textbf{Length of branch:} The Euclidean distance between the starting point and the terminal point;
\item \textbf{Width of branch:} The value in the distance map obtained in Section~\ref{sec:Pre-processing};
\item \textbf{Branching angle:} The angle between the parent and child branches, as illustrated by $\alpha$ in Figure~\ref{fig:angles};
\item \textbf{Divergence angle:} The angle describing the child's diverging degree from the plane spanned by its parent and grandparent, as illustrated by $\beta$ in Figure~\ref{fig:angles}.
\end{enumerate}

Each parameter is extracted for every branch in the 3D skeleton. It is recorded in an ordered list so that it can be located in the right position during the L-system parsing process. After the extraction of the parameter values, a least square fitting on the existing parameter values is used to give an estimation for future growth.

\begin{figure}
\centering

\begin{tikzpicture}[path fading=south]

%help line
%\draw[help lines, gray] (0,0,0) grid (5,5,5);

%rectangle bkg
\path[fill=gray, semitransparent, path fading=north]
(-1.5,0,-2) -- (3,0,-2) -- (3,0,3) -- (-1.5,0,3);
\node[gray, above] at (-1.5,0,3) {$P$};

%branches
\draw[red, ->] (0,0,0) to node[left] {$\vec{g}$} (0,1.732,0);
\draw[green, ->] (0,1.732,0) to node[anchor=south east] {$\vec{p}$} (1,2.732,1);
\draw[purple, ->] (1,2.732,1) to node[below] {$\vec{c}$} (2.6583,3.232,1);
\draw[purple, ->] (1,2.732,1) to (1,4.146,0);
\draw[green, ->] (0,1.732,0) to (-1,3.146,0);

%vlines
\draw[loosely dashed, green] (1,2.732,1) to (1,0,1);
\draw[loosely dashed, purple] (2.6583,3.232,1) to (2.6583,0,1);

%projective branches
\draw[densely dashed, green, ->] (0,0,0) to node[anchor=north east] {$\vec{q}$} (1,0,1);
\draw[densely dashed, purple, ->] (1,0,1) to node[above] {$\vec{d}$} (2.6583,0,1);

%extented lines
\draw[green, densely dashed] (1,2.732,1) to (2.5,4.232,2.5);
\draw[green, densely dashed] (1,0,1) to (2.5,0,2.5);

%arcs
\draw[blue, densely dashed] (1.4787,2.8763,1) arc (10.6523:39.5:0.5);
\node[blue] at (1.732,3.15,1) {$\alpha$};
\draw[blue, densely dashed] (1.5,0,1) arc (0:-40:0.5);
\node[blue] at (1.732,-0.21,1) {$\beta$};

\end{tikzpicture}
\caption{Branch $g$ is the parent of branch $p$ who has a child branch $c$. Branching angle $\alpha$ of branch $c$ is the angle hold by vector $\vec{p}$ and $\vec{c}$. $P$ is a plane whose normal is vector $\vec{g}$. $\vec{q}$ and $\vec{d}$ are projections of $\vec{p}$ and $\vec{c}$ on $P$. Divergence angle $\beta$ of branch $c$ is the angle hold by $\vec{q}$ and $\vec{d}$.}
\label{fig:angles} %% label for entire figure
\end{figure}

%-------------------------------------------------------------------------
\section{Model generation}

The 3D tree model can be generated by the L-system extracted. The L-system is able to not only rebuild the visible trunks faithfully, but also give a reasonable speculation for those occluded trunks. The process of trunk generation is mainly controlled by a parameter \textbf{derivation length} of the L-system. Derivation length is the number of steps that the axiom will be rewritten by the productions. A derivation length $D$ is decided by the volume of visible trunks. Depending on the ratio of occluded parts in whole trunks, an increment $I$ should be added to $D$ to generate full trunks of the tree. Another issue of model generation is the crown. It concerns two parameters \textbf{leafing depth} and \textbf{leaf number per branch}. Leafing depth means how many levels of branches will have leaves and leaf number per branch means how many leaves will grow from every branch.

Figure~\ref{fig:tree} lists two tree models with one of the original images in the left, two perspectives in the middle and the right (for more perspectives, please see the supplemental video).
Their L-systems are listed in Table~\ref{tbl:lsystems}. The model in Figure~\ref{fig:tree:a} has $8$ values for each parameter of branch $r$, $7$ values for branch $1$ and $7$ values for branch $2$. It is generated with derivation step $10$ ($D = 6, I = 4$), leafing depth $2$ and leaf number per branch $9$. And the model in Figure~\ref{fig:tree:b} has $7$ values for each parameter of branch $r$ and $9$ values for branch $1$. It is generated with derivation step $7$ ($D = 5, I = 2$), leafing depth $3$, leaf number per branch $9$.

\begin{table}
\centering
\subtable{
\centering
\begin{tabular}{|c|l|}
\hline
$\textbf{Axiom}$ & \multicolumn{1}{|c|}{$\mathscr{P}$}\\
\hline\hline
& $r \rightarrow \{2, r, 1\}$;\\
{$r$} & $1 \rightarrow \{2, 2\}$;\\
& $2 \rightarrow \{1, r\};$\\
\hline
\end{tabular}
}
\subtable{
\centering
\begin{tabular}{|c|l|}
\hline
$\textbf{Axiom}$ & \multicolumn{1}{|c|}{$\mathscr{P}$}\\
\hline\hline
\multirow{2}*{$r$} & $r \rightarrow \{1, 1, 1\}$;\\
& $1 \rightarrow \{r, 1\}$;\\
\hline
\end{tabular}
}
\caption{The L-systems of trees in Figure~\ref{fig:tree}.}
\label{tbl:lsystems}
\end{table}

\begin{figure}
  \centering
  \subfigure[]{
    \begin{minipage}[c]{0.333\columnwidth}
\centering
    \includegraphics[width=\textwidth]{Figure/Tree1(a).jpg}
\end{minipage}%
\hfill
\begin{minipage}[c]{0.333\columnwidth}
\centering
    \includegraphics[width=\textwidth]{Figure/Tree1(b).jpg}
\end{minipage}%
\hfill
\begin{minipage}[c]{0.333\columnwidth}
\centering
    \includegraphics[width=\textwidth]{Figure/Tree1(c).jpg}
\end{minipage}%
    \label{fig:tree:a}}
  \subfigure[]{
    \begin{minipage}[c]{0.333\columnwidth}
\centering
    \includegraphics[width=\textwidth]{Figure/Tree2(a).jpg}
\end{minipage}%
\hfill
\begin{minipage}[c]{0.333\columnwidth}
\centering
    \includegraphics[width=\textwidth]{Figure/Tree2(b).jpg}
\end{minipage}%
\hfill
\begin{minipage}[c]{0.333\columnwidth}
\centering
    \includegraphics[width=\textwidth]{Figure/Tree2(c).jpg}
\end{minipage}%
    \label{fig:tree:b}}
  \caption{Left: source images; Middle and Right: two different perspectives of tree models.}
\label{fig:tree}
\end{figure}

L-system also provides the flexibility to simulate the tree growth by modifying the derivation length and the leafing depth. Figure~\ref{fig:growth} lists a tree at different ages.
The derivation length and leafing depth of the four trees from left to right are: $(2, 1)$, $(4, 2)$, $(9, 3)$ and $(13, 4)$.

%-------------------------------------------------------------------------
\section{Conclusions}

An approach of modeling trees is proposed through inverse extraction of L-systems from images.
The extracted L-system provides the flexibility to adjust the tree model and simulate the tree growth.
Experiments show that the method for inversely extracting L-system is feasible and promising.
However, robust and efficient methods for image segmentation and self-calibration for tree objects still need to be studied. That is the content of our future work.

\begin{figure}
  \centering
  \includegraphics[width=1\columnwidth]{Figure/growth.jpg}
  \caption{Growth simulation of a tree.}
  \label{fig:growth}
\end{figure}

\section*{Acknowledgements}

To Robert, for all the bagels.

\bibliographystyle{acmsiggraph}
\nocite{*}
\bibliography{template}
\end{document}
